package Tree;

import java.util.HashMap;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-25  07:25
 * @Description: TODO
 * @Version: 1.0
 */
public class 后序中序构建二叉树106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inlen = inorder.length;
        int postlen = postorder.length;
        if (inlen != postlen) {
            throw new RuntimeException("Incurrent input data");
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < inlen; i++) {
            hashMap.put(inorder[i], i);
        }
        return buildTree2(postorder, 0, postlen - 1, hashMap, 0, inlen - 1);
    }

    private TreeNode buildTree2(int[] postorder, int postleft, int postright, HashMap<Integer, Integer> hashMap, int inleft, int inright) {
        if (postleft > postright || inleft > inright) {
            return null;
        }
        int rootval = postorder[postright];
        TreeNode root = new TreeNode(rootval);
        int pIndex = hashMap.get(rootval);
        root.left = buildTree2(postorder, postleft, pIndex - inleft + postleft - 1, hashMap, inleft, pIndex - 1);
        root.right = buildTree2(postorder, pIndex - inleft + postleft, postright - 1, hashMap, pIndex + 1, inright);
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
